package com.yeung.swordoffer;

/**
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 * <p>
 * <p>
 * 注意:!!
 * 是 二叉搜索树
 * -> 左子树上的所有节点的值均小于它的根节点
 * <p>
 * 序列{5,7,6,9,11,10,8}是下图二叉搜索树的后序遍历结果。
 * :::
 * <p>
 * 判断序列{5,7,6,9,11,10,8}是否是二叉排序树的后序遍历。其中，8是根节点，{5,7,6}比8小是左子树，{9,11,10}比8大是右子树。
 * 判断{5,7,6}是否是二叉排序树，其中6是根节点，5比6小是左子树，7比6大是右子树。
 * 判断{9,11,10}是否是二叉排序树，其中10是根节点，9比10小是左子树，11比10大是右子树。
 */
public class 二叉搜索树的后序遍历序列 {
    public static void main(String[] args) {
//        int[] app = {4, 8, 6, 12, 16, 14, 10};
//        int[] app = {4, 6, 7, 5};
//        int[] app = {1, 2, 3, 4, 5};
        int[] app = {};
        boolean b = VerifySquenceOfBST(app);
        System.out.println(b);
    }

    public static boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) return false;
        if (sequence.length == 1) return true;
        int start = 0;
        int end = sequence.length - 1;
        boolean ver = vertify(sequence, start, end);
        return ver;
    }

    static boolean vertify(int[] sequence, int start, int end) {
        if (start >= end) return true;
        //确定根节点
        int root = sequence[end];
        //确定左右子树
        int leftEnd = start;//有可能没有左孩子,所以假设它从右孩子开始
        for (int i = start; i < end; i++) {
            if (sequence[i] > root) {
                leftEnd = i - 1;
                break;
            }
            if (i == end - 1)
                //无右孩子的情况
                leftEnd = end - 1;
        }
        //        判断右子树序列是否都大于根节点
        for (int k = leftEnd + 1; k < end; k++) {
            if (sequence[k] < root)
                return false;
        }

        //确定左子树的序列是否正确         //确定右子树的序列是否正确
        return vertify(sequence, start, leftEnd) && vertify(sequence, leftEnd + 1, end - 1);
    }
}
